package leetcode.simple.q350;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        int[] nums1 = {4, 9, 5, 4, 4};
        int[] nums2 = {9, 4, 9, 8, 4};
        int[] intersect = intersect4(nums1, nums2);
        System.out.println(Arrays.toString(intersect));
    }


    /**
     * 官方题解1
     * @param nums1
     * @param nums2
     * @return
     */
    public static int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        HashMap<Integer, Integer> m = new HashMap<>();
        for (int n : nums1) {
            m.put(n, m.getOrDefault(n, 0) + 1);
        }

        int k = 0;
        for (int n : nums2) {
            int cnt = m.getOrDefault(n, 0);
            if (cnt > 0) {
                nums1[k++] = n;
                m.put(n, cnt - 1);
            }
        }
        return Arrays.copyOfRange(nums1, 0, k);
    }

    /**
     * 按照官方题解1，自己写一遍
     * @param nums1
     * @param nums2
     * @return
     */
    public static int[] intersect2(int[] nums1, int[] nums2) {
        //保证nums1的数组长度最短
        if (nums1.length > nums2.length){
            return intersect2(nums2, nums1);
        }

        //将nums1映射到HashMap中
        Map<Integer, Integer> map = new HashMap();
        for (int n : nums1) {
            int value = map.getOrDefault(n, 0);
            map.put(n, value + 1);
        }

        //遍历数组2 nums2，与map进行比较
        int index = 0;
        for (int n : nums2) {
            int elementCount = map.getOrDefault(n, 0);
            if (elementCount > 0){
                //将nums2中的n放入到nums1中
                nums1[index++] = n;
                //更新map的映射值
                map.put(n, elementCount - 1);
            }
        }

        return Arrays.copyOf(nums1, index);
    }

    /**
     * 官方题解2
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersect3(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0, j = 0, k = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                ++i;
            } else if (nums1[i] > nums2[j]) {
                ++j;
            } else {
                nums1[k++] = nums1[i++];
                ++j;
            }
        }
        return Arrays.copyOfRange(nums1, 0, k);
    }

    /**
     * 根据官方题解2，自己手写一遍
     * @param nums1
     * @param nums2
     * @return
     */
    public static int[] intersect4(int[] nums1, int[] nums2) {
        //先对两个数组排序
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int len1 = nums1.length;
        int len2 = nums2.length;

        //定义三个指针变量，用来指向遍历的位置
        int i = 0, j = 0, k = 0;
        //定义一个数组，用来接收结果
        int[] result = len1 < len2 ? new int[nums1.length] : new int[nums2.length];

        //扫描两个数组
        while (i < len1 && j < len2){
            if (nums1[i] < nums2[j]){
                //往后移动
                i++;
            }else if (nums2[j] < nums1[i]){
                //往后移动
                j++;
            }else {
                //相等的情况，将数据加入结果数组中
                result[k] = nums1[i];
                //三个指针都往后移动
                i++;
                j++;
                k++;
            }
        }

        return Arrays.copyOf(result, k);
    }

}



